`:top

In `F33f`_`[complexity theory`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Computational_complexity_theory]`_`f, a `!time-constructible function`! is a function `*f`* from `F33f`_`[natural numbers`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Natural_numbers]`_`f to natural numbers with the property that `*f`*(`*n`*) can be constructed from `*n`* by a `F33f`_`[Turing machine`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Turing_machine]`_`f in the time of order `*f`*(`*n`*). The purpose of such a definition is to exclude functions that do not provide an upper bound on the runtime of some Turing machine.`:cite-ref-0-1-0[`F5bf`_`[1`#cite-note-0-1]`_`f]

>>Contents

• `F0af`_`[Time-constructible`#time-constructible]`_`f

• `F0af`_`[Fully time-constructable`#fully-time-constructable]`_`f

• `F0af`_`[Space-constructible`#space-constructible]`_`f

• `F0af`_`[Properties`#properties]`_`f

• `F0af`_`[Applications`#applications]`_`f

• `F0af`_`[References`#references]`_`f

-─

>>Time-constructible

Let the Turing machine be defined in the standard way, with an alphabet that includes the symbols 0 , 1 {\\displaystyle 0,1} . It has a standard input tape containing zeros except for an input string. Let 1 n {\\displaystyle 1^{n}} denote a string composed of n {\\displaystyle n} ones. That is, it's the `F33f`_`[unary representation`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Unary_numeral_system]`_`f. Let | n | {\\displaystyle |n|} be the binary representation.

There are two different definitions of a `!time-constructible function`!.

In the first definition, a function f {\\displaystyle f} is called time-constructible if there exists a Turing machine M {\\displaystyle M} , such that for all but finitely many n {\\displaystyle n} , M ( 1 n ) {\\displaystyle M(1^{n})} halts in O ( f ( n ) ) {\\displaystyle O(f(n))} steps.

In the second definition, a function f {\\displaystyle f} is called time-constructible if there exists a Turing machine M {\\displaystyle M} , such that for all but finitely many n {\\displaystyle n} , M ( 1 n ) = | f ( n ) | {\\displaystyle M(1^{n})=|f(n)|} and halts in O ( f ( n ) ) {\\displaystyle O(f(n))} steps.

The second definition may use M ( 1 n ) = 1 f ( n ) {\\displaystyle M(1^{n})=1^{f(n)}} instead, since the two can be interconverted in O ( f ( n ) ) {\\displaystyle O(f(n))} steps.`:cite-ref-0-1-1[`F5bf`_`[1`#cite-note-0-1]`_`f]

>>>Fully time-constructable

There is also a notion of a `!`*fully`* time-constructible function`!.

A function f {\\displaystyle f} is called fully time-constructible if there exists a Turing machine M {\\displaystyle M} , such that for all but finitely many n {\\displaystyle n} , M ( 1 n ) {\\displaystyle M(1^{n})} halts in `*exactly`* f ( n ) {\\displaystyle f(n)} steps.`:cite-ref-2-2-0[`F5bf`_`[2`#cite-note-2-2]`_`f] This definition is slightly less general than the first two but, for most applications, either definition can be used.`:cite-ref-1-3-0[`F5bf`_`[3`#cite-note-1-3]`_`f] The following equivalence theorem shows that these two concepts are equivalent for most functions used in practice:

Theorem.`:cite-ref-1-3-1[`F5bf`_`[3`#cite-note-1-3]`_`f] If f {\\displaystyle f} is a function such that there exists ϵ ϵ > 0 {\\displaystyle \\epsilon >0} such that, for all but finitely many n {\\displaystyle n} , f ( n ) ≥ ≥ ( 1 + ϵ ϵ ) n {\\displaystyle f(n)\\geq (1+\\epsilon )n} , then f {\\displaystyle f} is time-constructible iff it is fully time-constructible.

More succinctly, the condition states that f ( n ) − − n = Ω Ω ( n ) {\\displaystyle f(n)-n=\\Omega (n)} .

>>Space-constructible

Function f {\\displaystyle f} is called space-constructible, if there exists a Turing machine M {\\displaystyle M} , such that for all but finitely many n {\\displaystyle n} , M ( 1 n ) = | f ( n ) | {\\displaystyle M(1^{n})=|f(n)|} (or equivalently 1 f ( n ) {\\displaystyle 1^{f(n)}} ), while using O ( f ( n ) ) {\\displaystyle O(f(n))} space.`:cite-ref-0-1-2[`F5bf`_`[1`#cite-note-0-1]`_`f]

Equivalently, if there exists a Turing machine M {\\displaystyle M} , such that for all but finitely many n {\\displaystyle n} given 1 n {\\displaystyle 1^{n}} , halts in a configuration in which exactly f ( n ) {\\displaystyle f(n)} cells are not blank, and no other cell has been written to during its operation.`:cite-ref-1-3-2[`F5bf`_`[3`#cite-note-1-3]`_`f] This is sometimes called "fully space-constructible". However, the two definitions are equivalent.`:cite-ref-1-3-3[`F5bf`_`[3`#cite-note-1-3]`_`f]

>>Properties

All the commonly used functions (such as n , n 2 , 2 n , n ! {\\displaystyle n,n^{2},2^{n},n!} ) are time- and space-constructible, as long as f ( n ) = Ω Ω ( n ) {\\displaystyle f(n)=\\Omega (n)} . The construction is straightforward. For example, n 2 {\\displaystyle n^{2}} is constructed by one for-loop, while n 3 {\\displaystyle n^{3}} is constructed by two for-loops, etc.

If f ( n ) = o ( n ) {\\displaystyle f(n)=o(n)} is time-constructible, then it is eventually constant, since otherwise there is insufficient time to read the entire input.

ln ⁡ ⁡ n {\\displaystyle \\ln n} is space-constructible even though ln ⁡ ⁡ n = o ( n ) {\\displaystyle \\ln n=o(n)} .

For every recursive function f {\\displaystyle f} , there is a recursive function g {\\displaystyle g} which is time constructible and ∀ ∀ n , g ( n ) > f ( n ) {\\displaystyle \\forall n,g(n)>f(n)} .`:cite-ref-1-3-4[`F5bf`_`[3`#cite-note-1-3]`_`f]

>>Applications

Time-constructible functions are used in results from complexity theory such as the `F33f`_`[time hierarchy theorem`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Time_hierarchy_theorem]`_`f. They are important because the time hierarchy theorem relies on Turing machines that must determine in `*`F33f`_`[O`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Big-O_notation]`_`f`*(`*f`*(`*n`*)) time whether an algorithm has taken more than `*f`*(`*n`*) steps. This is, of course, impossible without being able to calculate `*f`*(`*n`*) in that time. Such results are typically true for all natural functions `*f`* but not necessarily true for artificially constructed `*f`*. To formulate them precisely, it is necessary to have a precise definition for `*a natural function f`* for which the theorem is true. Time-constructible functions are often used to provide such a definition.

Space-constructible functions are used similarly, for example in the `F33f`_`[space hierarchy theorem`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Space_hierarchy_theorem]`_`f.

>>References

`*This article incorporates material from constructible on `F33f`_`[PlanetMath`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=PlanetMath]`_`f, which is licensed under the Creative Commons Attribution/Share-Alike License.`*

`:cite-note-0-1`!1.`! `F0af`_`[↑`#cite-ref-0-1-0]`_`f `:citerefgoldreich2008`aGoldreich, Oded (2008). `*Computational Complexity: A Conceptual Perspective`*. Cambridge University Press. pp. 130, 139. `F33f`_`[ISBN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISBN_(identifier)]`_`f 978-0-521-88473-0.

`:cite-note-2-2`!2.`! `F0af`_`[↑`#cite-ref-2-2-0]`_`f `:citerefhomerselman2011`aHomer, Steven; Selman, Alan L. (2011). `*Computability and Complexity Theory`* (Second ed.). Springer. `F33f`_`[ISBN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISBN_(identifier)]`_`f 978-1-4614-0681-5.

`:cite-note-1-3`!3.`! `F0af`_`[↑`#cite-ref-1-3-0]`_`f `:citerefbalc-zard-azgabarr-1988`aBalcázar, José Luis; Díaz, Josep; Gabarró, Joaquim (1988). `*Structural Complexity I`*. Springer-Verlag. `F33f`_`[ISBN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISBN_(identifier)]`_`f 3-540-18622-0.

`c`F0af`_`[↑ Back to top`#top]`_`f`a